#pragma once
#include<vector>

using namespace std;

namespace PQ_YC
{
    template <class T, class Container = vector<T>>
    class priority_queue
    {
    public:
        priority_queue()
        {}
        
        void Adjustup(size_t son)
        {
            int parent = (son - 1) / 2;
            while (son)
            {
                if (_Con[parent] < _Con[son])
                {
                    swap(_Con[parent], _Con[son]);
                    son = parent;
                    parent = (son - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }

        void Adjustdown(size_t parent)
        {
            int son = parent * 2 + 1;

            while (son < _Con.size())
            {
                if (son + 1 < _Con.size() && _Con[son] < _Con[son + 1])
                    son++;

                if (_Con[son] > _Con[parent])
                {
                    swap(_Con[son], _Con[parent]);
                    parent = son;
                    son = parent * 2 + 1;
                }
                else
                {
                    break;
                }
            }
        }

        bool empty() const
        {
            return _Con.empty();
        }

        size_t size() const
        {
            return _Con.size();
        }

        const T& top() const
        {
            return _Con[0];
        }

        void push(const T& x)
        {
            _Con.push_back(x);
            Adjustup(_Con.size() - 1);
        }

        void pop()
        {
            swap(_Con[0], _Con[_Con.size() - 1]);
            _Con.pop_back();
            Adjustdown(0);
        }
    private:
        Container _Con;
    };

    void TestPriority_queue01()
    {
        priority_queue<int> pq1;
        pq1.push(10);
        pq1.push(8);
        pq1.push(6);
        pq1.push(7);
        pq1.push(4);
        pq1.push(3);
        pq1.push(2);
        pq1.push(5);
        pq1.push(1);

        while (pq1.size())
        {
            int top = pq1.top();
            pq1.pop();

            cout << top << ' ';
        }
        cout << endl;
    }
};